import java.util.*;

class Solution1 {
    public int lastStoneWeight(int[] stones) {
        if(stones.length == 0) return 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int x:stones) {
            queue.add(x);
        }
        queue.add(0);
        while(queue.size()>1) {
            int y = queue.poll();
            int x = queue.poll();
            if(x < y) {
                queue.add(y - x);
            }
        }
        return queue.poll();
    }
}

// 5 8 9 10

class KthLargest1 {
    PriorityQueue<Integer> queue = null;

    public KthLargest1(int k, int[] nums) {
        queue = new PriorityQueue<>(k);
        for(int i =0; i<k && i<nums.length; i++) {
            queue.offer(nums[i]);
        }
        if(nums.length > k) {
            for(int i = 0; i<nums.length - k; i++) {
                queue.offer(Integer.MIN_VALUE);
            }
        }
        for(int i = k; i<nums.length; i++) {
            if(nums[i] >= queue.peek()) {
                queue.poll();
                queue.add(nums[i]);
            }
        }
    }

    public int add(int val) {
        if(val > queue.peek()) {
            queue.poll();
            queue.add(val);
        }
        return queue.peek();
    }
}

class KthLargest {
    PriorityQueue<Integer> queue = null;
    int k;

    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;
        for(int x:nums) {
            queue.offer(x);
            if(queue.size() > k) {
                queue.poll();
            }
        }
    }

    public int add(int val) {
        queue.offer(val);
        if(queue.size() > k) {
            queue.poll();
        }
        return queue.peek();
    }
}

class Solution2 {
    public List<String> topKFrequent(String[] words, int k) {
        //1.统计每个单词出现的频次
        Map<String,Integer> map = new HashMap<>();
        for(String str:words) {
            map.put(str,map.getOrDefault(str,0)+1);
        }

        //2.建大小为k的小根堆
        PriorityQueue<Map.Entry<String ,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue()!=o2.getValue()) {
                    return o1.getValue() - o2.getValue();
                }else {
                    //出现频次相等则根据字典序比较
                    return o1.getKey().compareTo(o2.getKey());
                }
            }
        });

        for(Map.Entry<String,Integer> entry :map.entrySet()) {
            heap.add(entry);
            if(heap.size()>k) {
                heap.poll();
            }
        }
        //3.得到结果
        List<String> list = new LinkedList<>();
        while(!heap.isEmpty()) {
            System.out.println(heap.peek().getKey());
            list.add(heap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}

class MedianFinder1 {
    int[] nums = null;
    int size;
    public MedianFinder1() {
        size = 0;
        nums = new int[100003];
    }

    public void addNum(int num) {
        Arrays.sort(nums,0,size);
        nums[size++] = num;
    }

    public double findMedian() {

        if(size%2 == 1) {
            return nums[size/2];
        }
        return (nums[size/2] + nums[size/2+1])/2.0;
    }
}

class MedianFinder {
    PriorityQueue<Integer> left = null;
    PriorityQueue<Integer> right = null;

    public MedianFinder() {
        left = new PriorityQueue<>((a,b)->b-a);
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if(left.size() == right.size()) {
            if(left.isEmpty() || num<=left.peek()) {
                left.add(num);
            }else {
                right.add(num);
                left.add(right.poll());
            }
        }else {
            if(num > left.peek()) {
                right.add(num);
            }else {
                left.add(num);
                right.add(left.poll());
            }
        }
    }

    public double findMedian() {
        if(left.size() == right.size()) return (left.peek() + right.peek()) /2.0;
        else return left.peek();
    }
}

public class Test {
    public static void main(String[] args) {

    }
}
